We consider a generalization of the 0-1 knapsack problem in which the profit of each item can take any value in a range characterized by a minimum and a maximum possible profit. A set of specific profits is called a scenario. Each feasible solution associated with a scenario has a regret, given by the difference between the optimal solution value for such scenario and the value of the considered solution. The interval min-max regret knapsack problem (MRKP) is then to find a feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a practical point of view. Its decision version is complete for the second level of the polynomial hierarchy hence it is most probably not in N P. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an N P-hard problem. We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP. We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm and evaluate their performance through extensive computational experiments.
Heuristic and exact algorithms for the interval min-max regret knapsack problem / Furini, F.; Iori, M.; Martello, S.; Yagiura, M.. - In: INFORMS JOURNAL ON COMPUTING. - ISSN 1091-9856. - 27:2(2015), pp. 392-405. [10.1287/ijoc.2014.0632]
Heuristic and exact algorithms for the interval min-max regret knapsack problem
Furini F.;
2015
Abstract
We consider a generalization of the 0-1 knapsack problem in which the profit of each item can take any value in a range characterized by a minimum and a maximum possible profit. A set of specific profits is called a scenario. Each feasible solution associated with a scenario has a regret, given by the difference between the optimal solution value for such scenario and the value of the considered solution. The interval min-max regret knapsack problem (MRKP) is then to find a feasible solution such that the maximum regret over all scenarios is minimized. The problem is extremely challenging both from a theoretical and a practical point of view. Its decision version is complete for the second level of the polynomial hierarchy hence it is most probably not in N P. In addition, even computing the regret of a solution with respect to a scenario requires the solution of an N P-hard problem. We examine the behavior of classical combinatorial optimization approaches when adapted to the solution of the MRKP. We introduce an iterated local search approach and a Lagrangian-based branch-and-cut algorithm and evaluate their performance through extensive computational experiments.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.